nowcoder163 A-Fruit Ninja（计算几何+随机算法）

发表于 | 更新于: | 分类于 ， | | 阅读次数: |
字数统计: 565 | 阅读时长 ≈ 3

描述

传送门：A-Fruit Ninja

Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy,
splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.
Fruit Ninja is a very popular game on cell phones where people can enjoy cutting the fruit by touching the screen.
In this problem, the screen is rectangular, and all the fruits can be considered as a point. A touch is a straight line cutting
thought the whole screen, all the fruits in the line will be cut.
A touch is EXCELLENT if $ \dfrac {M}{N} $ ≥ x, (N is total number of fruits in the screen, M is the number of fruits that cut by the touch, x is a real number.)
Now you are given N fruits position in the screen, you want to know if exist a EXCELLENT touch.

输入描述

The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
The first line of each case contains an integer N (1 ≤ N ≤ 104) and a real number x (0 < x < 1), as mentioned above.
The real number will have only 1 digit after the decimal point.
The next N lines, each lines contains two integers xi and yi (-109 ≤ xi,yi ≤ 109), denotes the coordinates of a fruit.

输出描述

For each test case, output “Yes” if there are at least one EXCELLENT touch. Otherwise, output “No”.

示例

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
2
5 0.6
-1 -1
20 1
1 20
5 5
9 9
5 0.5
-1 -1
20 1
1 20
2 5
9 9

输出

1
2
Yes
No

题解

题目大意

给你n个点，再给你一个p（数据保证0 < p < 1，且p只有1位小数），问是否满足图中有n*p个点在一条直线上

思路

随机两个点，然后再看其它所有点 是否在这条直线上即可，随机1000+AC没问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef struct{
	int x;
	int y;
}Point;
Point s[20005];
int Xc(int x1, int y1, int x2, int y2){
	return x1*y2-x2*y1;
}
int main(){
	double x;
	int n, T, i, cnt, a, b, ans;
	scanf("%d", &T);
	while(T--){
		scanf("%d%lf", &n, &x);
		for(i=1;i<=n;i++)
			scanf("%d%d", &s[i].x, &s[i].y);
		cnt = 1111;
		while(cnt--){
			ans = 0;
			a = rand()%n, b = rand()%n;
			if(a==b)
				continue;
			for(i=1;i<=n;i++){
				if(Xc(s[i].x-s[a].x, s[i].y-s[a].y, s[b].x-s[a].x, s[b].y-s[a].y)==0)
					ans++;
			}
			if(10*ans >= 10*x*n){
				printf("Yes\n");
				break;
			}
		}
		if(cnt==-1)
			printf("No\n");
	}
}